package demo.practice.leetcode;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class P102 {
//给你一个二叉树，请你返回其按 层序遍历 得到的节点值。
    //https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
    public static void main(String[] args) {
        //
        //[3,9,20,null,null,15,7]
        //      3
        //    9   20
        //       15 7

        TreeNode root = new TreeNode(3);
        root.left= new TreeNode(9);
        root.right=new TreeNode(20);
        root.right.left=new TreeNode(15);
        root.right.right=new TreeNode(7);

        P102 p102 = new P102();
        p102.levelOrder(root);


    }
        public List<List<Integer>> levelOrder(TreeNode root) {

            LinkedList<TreeNode> list=new LinkedList<>();
            List<List<Integer>> valsarr= new ArrayList<>();
            if(root==null)
                return valsarr;
            list.push(root);

            while (list.size()!=0){
                List<TreeNode> nodes= new ArrayList<>();
                List<Integer> vals= new ArrayList<>();
                while (list.size()!=0){
    //                TreeNode poll = list.pop()    //Retrieves and removes the head (first element) of this list.
    //                System.out.println(poll.val);
                    TreeNode e = list.remove();//remove head

                    vals.add(e.val);
                    nodes.add(e);
                }

                nodes.forEach(i->{
                    if(i.left!=null)
                        list.add(i.left);  //list.push(i.left); add first
                    if(i.right!=null)
                        list.add(i.right);  //add last
                });
                valsarr.add(vals);
            }

            return valsarr;

        }


    public void foreach(TreeNode root){
        LinkedList<TreeNode> list=new LinkedList<>();
        list.push(root);
        while (list.size()!=0){
            List<TreeNode> nodes= new ArrayList<>();
            while (list.size()!=0){
                TreeNode poll = list.poll();
                System.out.println(poll.val);
                nodes.add(poll);
            }

            nodes.forEach(i->{
                if(i.left!=null)
                    list.push(i.left);
                if(i.right!=null)
                    list.push(i.right);
            });

        }

    }
}
